import org.w3c.dom.Node;

import javax.sound.midi.Soundbank;
import java.sql.Array;
import java.util.*;

/**
 * ClassName: Tree
 * Package: PACKAGE_NAME
 * Description:
 *
 * @Author MLH
 * @Create 2023/6/7 13:46
 * @Version 1.0
 */
public class Tree {

    public static void main(String[] args) {
        TreeNode root = buildTree(data);
        System.out.println("二叉树中序遍历结果如下：");
        lookTree(root);
        System.out.println("请输入一个数字：");
        Scanner scan = new Scanner(System.in);
        int number = scan.nextInt();
        List<Integer> list = positionTree(number, data);
        if (list.size() == 0){
            System.out.println("data：" + number + " not exist");
        }else {
            System.out.print("data：" + number + " position：");
            for (Integer i : list){
                System.out.print(i + " ");
            }
        }
    }

    //创建一个数组并赋值
    private static int[] data = new int[]{5,8,1,9,6,3,2,4,8,7};

    //定义一个二叉树
    static class TreeNode{
        private int val;
        //重合节点个数
        private int sum;
        private TreeNode left;
        private TreeNode right;

        public TreeNode(int val, int sum, TreeNode left, TreeNode right) {
            this.val = val;
            this.sum = sum;
            this.left = left;
            this.right = right;
        }

        public int getVal() {
            return val;
        }

        public void setVal(int val) {
            this.val = val;
        }

        public int getSum() {
            return sum;
        }

        public void setSum(int sum) {
            this.sum = sum;
        }

        public TreeNode getLeft() {
            return left;
        }

        public void setLeft(TreeNode left) {
            this.left = left;
        }

        public TreeNode getRight() {
            return right;
        }

        public void setRight(TreeNode right) {
            this.right = right;
        }
    }

    //构造排序二叉树
    public static TreeNode buildTree(int[] data){
        if (data.length < 1){
            return null;
        }
        TreeNode root = new TreeNode(data[0], 1, null, null);
        for (int i = 1; i < data.length; i++){
            TreeNode node = new TreeNode(data[i], 1, null, null);
            boolean result = compareNode(root, node);
            if (result != true){
                System.out.println("节点插入失败");
            }
        }
        return root;
    }
    //确定节点位置
    public static boolean compareNode(TreeNode root,  TreeNode node){
        if (root.getVal() == node.getVal()){
            root.setSum(root.getSum() + 1);
            return true;
        }
        if (root.getVal() > node.getVal() && root.getLeft() == null){
            root.setLeft(node);
            return true;
        }else if (root.getVal() < node.getVal() && root.getRight() == null){
            root.setRight(node);
            return true;
        }else if (root.getVal() > node.getVal() && root.getLeft() != null){
            return compareNode(root.getLeft(), node);
        }else {
            return compareNode(root.getRight(), node);
        }
    }

    //中序遍历二叉树
    public static void lookTree(TreeNode root){
        if (root.getLeft() != null){
            lookTree(root.getLeft());
        }
        System.out.println(root.getVal() + " " + root.getSum());
        if (root.getRight() != null){
            lookTree(root.getRight() );
        }
    }

    //根据输入的数字查询其在二叉树的位置
    public static List<Integer> positionTree(int data, int[] array){
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < array.length; i++){
            if (data == array[i]){
                int position = i + 1;
                list.add(position);
            }
        }
        return list;
    }



}
